package org.example.code.test2024.nine_mouth;

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

class MedianFinder {
    private Queue<Integer> minQueue;
    private Queue<Integer> maxQueue;

    public MedianFinder() {
        minQueue = new PriorityQueue<>(Collections.reverseOrder());
        maxQueue = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        maxQueue.offer(num);
        minQueue.offer(maxQueue.poll());
        if (minQueue.size() > maxQueue.size()) {
            maxQueue.offer(minQueue.poll());
        }
    }
    
    public double findMedian() {
        if(minQueue.size() < maxQueue.size()) {
            return maxQueue.peek();
        }else {
            return (minQueue.peek()+maxQueue.peek())/2.0;
        }
    }
}